# Definition for singly-linked list.
class ListNode(object):
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution(object):
    def insertionSortList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if not head: return head
        newHead = ListNode(None)
        newHead.next = head
        i = newHead
        while i.next:
            j = i.next
            prej = i
            minj = j
            preminj = prej
            while j:
                if j.val<minj.val:
                    minj = j
                    preminj = prej
                prej = j
                j = j.next
            preminj.next = minj.next
            minj.next = i.next
            i.next = minj
            i = i.next
        return newHead.next

head = ListNode(0)
Solution().insertionSortList(head)